<?php

/**
 * 单链表
 */

/**
 * 节点类
 */
class Node
{
    public $data;//节点数据
    public $next;//后继节点
    
    /**
     * 初始化
     *
     * @param string $data 节点数据
     *
     * @return mixed
     */
    public function __construct($data)
    {
        $this->data = $data;
        $this->next = NULL;
    }
}

/**
 * 逻辑实现
 */
class SingleLinkedList
{
    public $header;//头节点
    
    /**
     * 初始化
     *
     * @param string $data 节点数据
     *
     * @return mixed
     */
    public function __construct($data)
    {
        $this->header = new Node($data);
    }
    
    /**
     * 查找节点
     *
     * @peram string $item 查找的节点数据
     *
     * @return object
     */
    public function find($item)
    {
        $current = $this->header;
        while($current->data != $item)
        {
            $current = $current->next;
        }
        return $current;
    }
    
    /**
     * 在节点后插入新节点
     *
     * @param string $item 当前的节点数据
     * @param object $new  新插入的节点数据
     *
     *                     A->B->D
     *                         C
     * @return boolean
     */
    public function insert($item,$new)
    {
        $new_node = new Node($new);
        $item_node = $this->find($item);
        $new_node->next  = $item_node->next;//当前节点的后继节点赋值到新节点额后继节点
        $item_node->next = $new_node;//新节点赋值给当前节点的后继节点
        return true;
    }
    
    /**
     * 更新节点
     *
     * @param string $old 老节点数据
     * @param string $new 要更新的节点数据
     *
     * @return true
     */
    public function update($old,$new)
    {
        $current = $this->header;
        while($current->next == NULL)
        {
            echo '这个一个空的链表';
            return false;
        }
        
        while($current->next != NULL)
        {
            if ($current->data == $old)
            {
                break;
            }
            
            $current = $current->next;
        }
        
        $current->data = $new;
        return true;
    }
    
    /**
     * 查找当前节点的前一个节点
     *
     * @param string $item 当前节点数据
     *
     * @return boolean
     */
    public function findPreByCurrentNode($item)
    {
        $current = $this->header;
        while($current->next != NULL && $current->next->data != $item)
        {
            $current = $current->next;
        }
        
        return $current;
    }
    
    /**
     * 删除一个节点
     *
     * @param string $item 当前删除节点数据
     *
     * @return boolean
     */
    public function delete($item)
    {
        $pre_node = $this->findPreByCurrentNode($item);
        if ($pre_node->next != NULL)
        {
            $pre_node->next = $pre_node->next->next;
        }
        
        return true;
    }
    
    /**
     * 清空链表
     */
    public  function clear()
    {
        $this->header = NULL;
    }
    
    /**
     * 显示链表
     */
    public function show()
    {
        $current = $this->header;
        while($current->next == NULL)
        {
            echo '这个一个空的链表';
            return;
        }
        
        while($current->next != NULL)
        {
            echo $current->next->data."  ";
            $current = $current->next;
        }
        return;
    }
}

//插入
$single_linked_list = new SingleLinkedList('header');
$single_linked_list->insert('header','A');
$single_linked_list->insert('A','B');
$single_linked_list->insert('B','C');
$single_linked_list->insert('C','D');
$single_linked_list->show();
echo PHP_EOL;

//删除
$single_linked_list->delete('C');
$single_linked_list->show();

echo PHP_EOL;

//更新
$single_linked_list->update('D',"E");
$single_linked_list->show();

echo PHP_EOL;
$single_linked_list->clear();
$single_linked_list->show();
